//
// Created by francklinson on 2021/9/17 AT 22:50.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>

using namespace std;

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>> &intervals) {
        if (intervals.empty())
            return 0;
        // 根据右边界的大小排序
        sort(intervals.begin(), intervals.end(), [](vector<int> &a, vector<int> &b) {
            return a[1] < b[1];
        });
        int n = (int) intervals.size();
        int right = intervals[0][1];
        int ans = 1; // 计算最多能有几个区间
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] >= right) { // 一个新区间
                ++ans;
                right = intervals[i][1];
            }
        }
        return n - ans; //剩下的是需要删除掉的区间
    }
};

int main() {
    vector<vector<int>> intervals{{1, 2},
                                  {2, 3},
                                  {3, 4},
                                  {1, 3}};
    Solution solution;
    cout << solution.eraseOverlapIntervals(intervals) << endl;
    return 0;
}

